package LeetCode.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　

		Implement int sqrt(int x).
	
	Compute and return the square root of x.
	
题目大意

	求一个数的平方根

解题思路
	
	公理：对于一个非负数n，它的平方根不会大于（n/2+1）
		那么就遍历  0~n/2+1 中的所有的数
			假设当前遍历到的数为num：计算num*num是否等于n
	为提高搜索效率：使用二分法搜索
	
 * @Date 2017-09-17 14：42
 */
public class _069_Sqrt_x {
	
    public int mySqrt(int x) {
    	int upLimit = x/2+1;		//上限
    	//二分搜索：两个指针
    	int lo = 0, hi = upLimit;
    	long mid = 0;
    	while (lo <= hi) {
    		mid = (lo + hi) / 2;	//二分法查找mid就是我们要找的值
    		long  sq = (long) (mid * mid);
    		if (sq == x) {
    			return (int) mid;
    		} else if (sq > x) {
    			hi = (int)mid-1;
    		} else {
    			lo = (int)mid+1;
    		}
    	}	
    	return (int) hi;					//如果没有精确的平方根，找到最接近的一个eg：sqrt(26)=5
    }
    
	public static void main(String[] args) {
		_069_Sqrt_x obj = new _069_Sqrt_x();
		LogUtils.println("平方根", obj.mySqrt(3));
	}

}
